松本行弘的程序世界 10 高速执行和并行处理

让程序高速执行（前篇）

是不是越快越好

并不是视速度最优先就一定好。预算、开发效率和开发周期等制约因素也在性能权衡范围之内。

高速执行的乐趣与效率

在进行性能优化之前，必须确认是否真有必要提高速度。速度提高到什么程度也要事先估算。

以数据为基础做出判断

改善系统调用

排序处理任务重时，典型的对策是使用施瓦茨变换。

数据可靠吗

误差

只需改善瓶颈

性能优化中，“因为是排序，所以就用施瓦茨变换”这种条件反射式的对策并非总管用。为了合理提高速度，确立恰当的策略是很必要的。
帕累托法则又称80/20法则，即80%的数值是由20%的构成要素产生的。由帕累托法则可知，有20%的努力可以达到巨大回报，而有80%的努力得不到多少回报。在得不到回报的地方，不管怎么努力都是徒劳的。
Donald Knuth也提到，通常一半以上的执行时间都耗费在程序中不到4%的部分。
这些耗费了大半以上执行时间的部分称为瓶颈。
判定瓶颈，可以用profiler这一工具。

profiler本身成了累赘

不确定性原理是指测定行为本身对被测对象产生了影响，从原理上可以说不可能正确知道对象的状态。但是知道实际状态的大体倾向。

算法与数据结构

选择合适的算法，这是性能改善的第一考虑因素，要记住这条铁则。

理解O记法

如何从效率方面判定一个算法的好坏呢。一个方法就是O记法，表示某种算法对于变量（比如使用的元素个数）如何变化。

选择算法

调查算法的性能

Ruby提供进行算法性能比较时用的benchmark程序。

高速执行的悲哀

徒劳无益的努力

很容易在瓶颈无关的地方花费太多徒劳无益的努力。

改良绊住了手脚

sort_by所依据的施瓦茨变换，是用时间和空间的交换来消减计算量的方法。sort_by方法与sort方法相比，占用了多达三倍以上的内存。所以，模块内的处理本来不是很重，如果一味地占用内存反而可能会变慢。
性能优化，光有理论还不行，如果不实际做的话就不知道到底什么是正确的。

算法选择的圈套

在进行性能优化时，不改变原来程序的执行时一个大原则。

性能优化的格言

过早的优化是万恶之源。

优化有两条准则。
1.别做优化
2.（仅适用于专家）先不要做优化

过早的优化是万恶之源
代码优化的好处多多，但是这并不意味着所有的代码都需要进行优化，有时过度的优化反而适得其反——费时、费力、不讨好。
“现代计算机科学的鼻祖”Donald Knuth曾说过“过早的优化是万恶之源”，因为：让正确的程序更快，要比让快速的程序正确容易得多。
在项目开发中，总是有程序员浪费宝贵的时间去改进那些不需要改进的代码，而没有通过所做的改进增加价值。在对项目进行优化时，究竟哪些地方应该优化，应该如何优化，哪些不应该优化呢？你需要先来了解一下本文所说的这7件事。
1.究竟要优化什么？
在优化工作开始的时候，你还尚未明确优化内容和目的，那么你很容易陷入误区。在一开始，你就应该清楚地了解你要达到的效果，以及其他优化相关的各种问题。这些目标需要明确指出（至少精通技术的项目经理可以理解和表达它），接下来，在整个优化过程中，你需要坚持这些目标。
在实际的项目开发中，经常会存在各种各样的变数。可能一开始时要优化这一方面，随后你可能会发现需要优化另一方面。这种情况下，你需要清晰地了解这些变化，并确保团队中的每个人都明白目标已经发生了变化。
2.选择一个正确的优化指标
选择正确的指标，是优化的一个重要组成部分，你需要按照这些指标来测量优化工作的进展情况。如果指标选择不恰当，或者完全错误，你所做的努力有可能白费了。
即使指标正确，也必须有一些辨别。在某些情况下，将最多的努力投入到运行消耗时间最多的那部分代码中，这是实用的策略。但也要记住，Unix/Linux内核的大部分时间花费在了空循环上。
需要注意的是，如果你轻易选择了一个很容易达到的指标，这作用不大，因为没有真正解决问题。你有必要选择一个更复杂的、更接近你的目标的指标。
3.优化在刀刃上
这是有效优化的关键。找到项目中与你的目标（性能、资源或其他）相背的地方，并将你的努力和时间用在那里。
举一个典型的例子，一个Web项目速度比较慢，开发者在优化时将大部分精力放在了数据库优化上，最终发现真正的问题是网络连接慢。
另外，不要分心于容易实现的问题。这些问题尽管很容易解决，但可能不是必要的，或与你的目标不相符。容易优化并不意味着值得你花费工夫。
4.优化层次越高越好
在一般情况下，优化的层次越高，就会越有效。根据这个标准，最好的优化是找到一个更有效的算法。
举个例子，在一个软件开发项目中，有一个重要的应用程序性能较差，于是开发团队开始着手优化，但性能并没有提升太多，之后，项目人员交替，新的开发人员在检查代码时发现，性能问题的核心是由于在表中使用了冒泡排序算法，导致成千上万项的增加。
尽管如此，高层次的优化也不是“银弹”。一些基本技术，如将所有东西移到循环语句外，也可以产生一些优化的效果。通常情况下，大量低层次的优化可以产生等同于一个高层次优化的效果。
还需要注意的是，高层次优化，会减少一些代码块，那么你之前对这些代码块所做的优化就没有任何意义了，因此，刚开始就应该考虑高层次的优化。
5.不要过早优化
在项目早期就进行优化，会导致你的代码难以阅读，或者会影响运行。另一方面，在项目后期，你可能会发现之前所做的优化没有起到任何作用，白白浪费了时间和精力。
正确的方式是，你应该将项目开发和优化当作两个独立的步骤来做。
6.依赖性能分析，而不是直觉
你往往会认为你已经知道哪里需要优化，这是不可取的，尤其是在复杂的软件系统中，性能分析数据应该是第一位的，最后才是直觉。
优化的一个有效的策略是，你要根据所做工作对优化效果的影响来进行排序。在开始工作之前找到影响最大的“路障”，然后再处理小的“路障”。
7.优化不是万金油
优化最重要的规则之一是，你无法优化一切，甚至无法同时优化两个问题。比如，优化了速度，可能会增加资源利用；优化了存储的利用率，可能会使其他地方放慢。你需要权衡一下，哪个更符合你的优化目标。

让程序高速执行（后篇）

例题是曼德勃罗集合的计算程序，指复平面上满足以下条件的复素数的集合：经过某种反复迭代运算以后，其值不会发散到无限大。

确认程序概要

发现瓶颈

使用profiler

使用更好地profiler

ruby-prof程序通过使用扩展库可以实现高速profile

高速优化之一：消减对象

Ruby高速优化的规则。

减少对象

高级面向对象语言中对象的生成要花费一定的时间，减少对象，除了会降低生成成本外，还有别的好处。
Ruby中不在使用的对象，由被称作垃圾收集的处理自动进行回收。垃圾收集处理需要检查对象的引用关系，任何地方都不再引用的对象会被判定为已经不再使用了。当对象的数量很多时，判断成本就要增大。

减少方法调用

方法调用中，存在多态性这一面向对象的本质特征，先要评价参数，判定对象种类，然后选出一个合适的方法，再讲控制交给该方法，这是一个缓慢的处理过程。
为了避开方法调用，尽可能不用Ruby中实现的方法。Ruby中实现的方法，几乎所有的情况都是调用其他方法来实现的。也就是说，只要使用了一次Ruby中实现的方法，就会有多余的方法调用发生。

高速优化之二：利用立即值

Ruby中有几类对象并不实际分配内存，而是用引用本身来表示，这种值称为立即值。
现在的Ruby中，小的整数（±2 ^30以内）、真假值、nil和符号名等都是立即值。
立即值既然不生成对象，就不用担心对象的生成成本，而且也不用垃圾收集处理，所以它具有特别理想的特性。

高速优化之三：利用C语言

Ruby是解释性语言，单纯计算的循环不是很快。如果将处理交给编译器，就可以变得很快。

高速优化之四：采用合适的数据结构

全部以C语言计算

还存在其他技巧

还有以空间换时间。

并行编程

使用线程的理由

与进程不同，同一进程的线程可以共享内存空间，所以，不同的线程能够引用同一对象。不需要经过将数据变为字节流再进行通信这样麻烦的处理，就能交换信息。

生成线程

线程的执行状态

Ruby的线程有四种状态。
run：执行中
stop：停止中
to_kill:终止处理中
killed:终止

传递值给线程的方法

信息共享所产生的问题

数据完整性丧失
死锁

与其说是线程的问题，不如说是并行处理本身的问题。

数据完整性的丧失

原子操作

死锁

哲学家进餐问题

用锁来实现对资源的独占

Ruby Mutex类，互斥锁。
Java中，方法定义声明为synchronize,该方法被调用时自动加锁。

二级互斥

很遗憾，锁的问题并不全是Mutex所能覆盖的单纯事例。如数据库中，对数据的访问需要以下多种互斥控制。

可以同时引用
禁止同时更新
禁止更新中引用
禁止引用中更新

引用与更新这种两个层次的互斥（二级互斥），在文件读取时也经常会发生。

数据库锁总结

数据库锁出现的原因是为了处理并发问题，因为数据库是一个多用户共享的资源，当出现并发的时候，就会导致出现各种各样奇怪的问题，就像程序代码一样，出现多线程并发的时候，如果不做特殊控制的话，就会出现意外的事情，比如“脏“数据、修改丢失等问题。所以数据库并发需要使用事务来控制，事务并发问题需要数据库锁来控制，所以数据库锁是跟并发控制和事务联系在一起的。

平时会经常看到或者听到数据库锁有“共享锁”，“排它锁”，“互斥锁”，“写锁”，“读锁”，“悲观锁”，“乐观锁”，“行级锁”，“表级锁”，“页级锁”等，同时我们还会常看到“丢失修改“，”不可重复读“，”读脏数据“这三个术语，他们究竟是什么关系以及怎么理解呢，下面就来介绍一下他们。

先说事务的特性，要想成为事务，必须满足：ACID（原子性，一致性，隔离性，持久性）四特性，事务是恢复和并发控制的基本单位。原子性指的是事务是数据库的逻辑工作单位，事务中操作要么都做，要么都不做；一致性指的是事务的执行结果必须是使数据库从一个一致性状态变大另一个一致性状态，一致性和原子性是密切相关的；隔离性指的是一个事务执行不能被其他事务干扰；持久性指的是一个事务一旦提交，他对数据库中数据的改变就是永久性的。

先说悲观锁和乐观锁吧。并发控制一般采用三种方法，分别是乐观锁和悲观锁以及时间戳。乐观锁认为一个用户读数据的时候，别人不会去写自己所读的数据；悲观锁就刚好相反，觉得自己读数据库的时候，别人可能刚好在写自己刚读的数据，其实就是持一种比较保守的态度；时间戳就是不加锁，通过时间戳来控制并发出现的问题。悲观锁就是在读取数据的时候，为了不让别人修改自己读取的数据，就会先对自己读取的数据加锁，只有自己把数据读完了，才允许别人修改那部分数据，或者反过来说，就是自己修改某条数据的时候，不允许别人读取该数据，只有等自己的整个事务提交了，才释放自己加上的锁，才允许其他用户访问那部分数据。乐观锁就比较简单了，就是不做控制，这只是一部分人对于并发所持有的一种态度而已。时间戳就是在数据库表中单独加一列时间戳，比如“TimeStamp”，每次读出来的时候，把该字段也读出来，当写回去的时候，把该字段加1，提交之前，跟数据库的该字段比较一次，如果比数据库的值大的话，就允许保存，否则不允许保存，这种处理方法虽然不使用数据库系统提供的锁机制，但是这种方法可以大大提高数据库处理的并发量，因为这种方法可以避免了长事务中的数据库加锁开销（操作员A 和操作员B操作过程中，都没有对数据库数据加锁），大大提升了大并发量下的系统整体性能表现。需要注意的是，乐观锁机制往往基于系统中的数据存储逻辑，因此也具备一定的局限性，如在上例中，由于乐观锁机制是在我们的系统中实现，来自外部系统的用户余额更新操作不受我们系统的控制，因此可能会造成脏数据被更新到数据库中。在系统设计阶段，我们应该充分考虑到这些情况出现的可能性，并进行相应调整（如将乐观锁策略在数据库存储过程中实现，对外只开放基于此存储过程的数据更新途径，而不是将数据库表直接对外公开）。以上悲观锁所说的加“锁”，其实分为几种锁，分别是：排它锁和共享锁，其中排它锁又称为写锁，共享锁又称为读锁。

共享锁和排它锁是具体的锁，是数据库机制上的锁，存在以下关系：

(x表示是排它锁(Exclusive)，s表示共享锁(Share)，Y表示yes，N表示no）

上图表示可以共存的锁，如，第二行表示，一个事务T1给某数据加了X锁，则事务T2就不能再给那数据加X锁了，同时也不能再加S锁了，只有到T1事务提交完成之后，才可以。默认来说，当sql脚本修改更新某条记录的时候，会给该条记录加X锁，读的话加的是S锁。
另外，并发操作会导致数据的不一致性，主要包括“丢失数据”，“不可重复读”，“读脏数据等。还有就是，并发控制会造成活锁和死锁，就像操作系统那样，会因为互相等待而导致。活锁指的是T1封锁了数据R，T2同时也请求封锁数据R，T3也请求封锁数据R，当T1释放了锁之后，T3会锁住R，T4也请求封锁R，则T2就会一直等待下去，这种处理方法就是采用“先来先服务”策略；死锁就是我等你，你又等我，双方就会一直等待下去，比如：T1封锁了数据R1，正请求对R2封锁，而T2封住了R2,正请求封锁R1，这样就会导致死锁，死锁这种没有完全解决的方法，只能尽量预防，预防的方法有：1一次封锁发，指的是一次性把所需要的数据全部封锁住，但是这样会扩大了封锁的范围，降低系统的并发度；2顺序封锁发，指的是事先对数据对象指定一个封锁顺序，要对数据进行封锁，只能按照规定的顺序来封锁，但是这个一般不大可能的。另外，系统如何判断出现死锁呢，毕竟出现死锁不能一直干等下去，要及时发现死锁同时尽快解决出现的死锁，诊断和判断死锁有两种方法，一是超时法，二是等待图法。超时法就是如果某个事物的等待时间超过指定时限，则判定为出现死锁；等待图法指的是如果事务等待图中出现了回路，则判断出现了死锁。对于解决死锁的方法，只能是撤销一个处理死锁代价最小的事务，释放此事务持有的所有锁，同时对撤销的事务所执行的数据修改操作必须加以恢复。

最后，说下行级锁和表级锁。锁包括行级锁和表级锁
行级锁是一种排他锁，防止其他事务修改此行。

用队列协调线程

使用锁对资源进行互斥控制，是线程间保证协调的一种机制。除了锁以外，为了保证协调，还有别的方法。
问题的根源在于多个进程访问同一资源，为了实现无共享，给每个资源准备一个管理用的线程，各线程间只能交换某些限定的信息。
线程间信息交换的方法有代表性的有信息存储，信道及队列。

这里的生产者消费者问题并不是典型的生成者消费者问题，而是做出了一定的限制，即生产速度小于消费速度。不锁buffer,仅做信息传递的通道来进行说明。

队列也可以用于解决资源的竞争。

锁模型与队列模型的比较

锁模型

如果竞争足够少，多数情况下能保持较高性能，对于资源的竞争，不能忘记加锁，要做到完美无缺较难。

队列模型

在竞争少的时候，其性能比不上锁模型，比锁模型更容易贯彻，会因线程增多而带来性能低下的恶果。

前景可期的并行编程技术，Actor

并行编程，要求有更高的抽象度和对人类而言更简单的编程模型。Actor（参与者模式）或许就是答案。

何谓Actor

所谓Actor，是（仅）通过消息（message）进行通信的实体。
与面向对象语言中对象的区别。向对象发送消息（方法调用），调用开始后，会一直等到返回结果，是一种同步方式。面向Actor发送消息，仅仅是发送消息而不返回结果，是一种异步方式。

1
2
3

同步(Synchronous)和异步(Asynchronous)
1.同步方法调用一旦开始，调用者必须等到方法调用返回后，才能继续后续的行为。
2.异步方法调用更像一个消息传递，一旦开始，方法调用就会立即返回，调用者就可以继续后续的操作。而，异步方法通常会在另外一个线程中，“真实”地执行着。整个过程，不会阻碍调用者的工作。

Actor由于仅仅通过消息进行信息交换，所以不能直接共享同一个值，信息传达要多花些代价。
Actor由于没有消息以外的信息传递手段，所以不用担心Actor之间的资源竞争。发送给Actor的消息都配送到各个Actor所拥有的邮箱里。多个消息同时到达时竞争由内嵌到系统中的排除机制来处理。
Actor的一大优点是安全，更大的优点是易懂。Actor根据消息进行处理，必要的化会向其他Actor传递消息，或向Actor返回消息。
这与现实世界中人与人之间相处没有多大的差别。现实世界中，别人在想什么你不知道，想要求什么时，需要通过某种手段传递“消息”。
理论上要到达最高性能，一般认为线程更优秀。但如果不注意使用线程的话，会出现与时机相关的很麻烦的问题。在计算机性能日益提高的今天，与理论上最高性能的可能性相比，Actor的安全性和易懂性更引人注目。

操作Actor的三种处理系统

Actor Model的函数型语言Erlang。
Erlang是只允许单一赋值的函数型语言，即一旦赋值，变量的值就不再改变。

Erlang的程序

pingpong处理的开始

启动pingpong程序

Erlang的错误处理

Erlang中通过发送消息来通知异常终止。收到消息的process（actor）料理死去的process后事。
有了这种机制，使得Erlang适合构造抗障碍性强的系统。

Erlang的使用场所

Erlang在通常的文本处理汇总并不怎么快。Erlang的好处在于其扩展性。对于多个处理并列执行的情况，分割成合适的Erlang process，能够发挥多CPU的威力。
同样的多任务分割虽然用操作系统的进程或线程也能实现，但Erlang的process与操作系统的进程或线程相比，能够轻量实现（1个process最小只耗费300字节），即使有大量process也不必顾虑、更进一步说，Erlang设计思想不用process连基本处理都不能实现，process分割在某种意义上可以说是强制的。

适合现代服务器端程序。

面向Ruby的库“Revactor”

Revactor的目的是为Ruby提供Erlang式的编程。
其优点是可以同时体验Ruby和Erlang的好处。但是Revactor中Actor的实现不是靠线程而是靠Fiber。Erlang的目的在于最大限度地利用多核CPU，而Revactor并不适合这种目的。
Revactor的最大优点，是能够在等待文件输入输出时，将程序的停止控制在最小程度。

另一个库Dramatis

Dramatis是Ruby中另一个Actor库。函数型语言Erlang不支持面向对象功能。用Ruby这样的面向对象语言来实现Actor的时候，即使用普通对象来实现Actor，也不可避免地会出现把方法调用和发送消息这两种类似概念混在一起的情况。Dramatis库就是解答这种“概念混淆”。